package 最小路径和;

import java.util.Map;

public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[][] grid = new int[][]{
                {1,3,1},{1,5,1},{4,2,1}
//                {1,2,3},{4,5,6}
        };
        System.out.println(solution.minPathSum(grid));

    }


    public int minPathSum(int[][] grid) {


        int m = grid.length;
        int n = grid[0].length;

        if(m == 1 || n ==1){
            int sum = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sum += grid[i][j];
                }
            }

            return sum;
        }
        //行
        for (int i = m -2; i >=0; i--) {
            grid[i][n-1] += grid[i+1][n-1];
        }
        //列
        for (int i = n-2; i >= 0; i--) {
            grid[m-1][i] += grid[m-1][i+1];
        }

        for (int i = m-2; i >= 0; i--) {
            for (int j = n-2; j >= 0; j--) {
                if( i == 0 && j == 0){
                    break;
                }
                grid[i][j] += Math.min(grid[i+1][j],grid[i][j+1]);
            }
        }

        return grid[0][0] + Math.min(grid[0][1],grid[1][0]);
    }


}
